package com.wen.Part6.GraphAlgorithm.impl;


import com.wen.Part6.DataStructure.Graph;
import com.wen.Part6.GraphAlgorithm.GraphAlgorithm;

import java.util.ArrayList;
import java.util.List;

/**
*@Description: 拓扑排序
*@date: 2021/7/10 21:35
**/
public class TopSort1 implements GraphAlgorithm {

    /*
    取没有访问过的，并且入度为0的点，标记为访问，并把可达点的入度减一

     */
    @Override
    public Graph solve(Graph g) {

        List<String> list = new ArrayList<>();
        int size = g.getSize();

        // 获取入度
        int[] inDegreeArray = g.getInDegreeArray();
        int[] visited = new int[size];

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if(inDegreeArray[j] == 0 && visited[j] == 0){  // 入度为0且没有访问过
                    visited[j] = 1;
                    list.add(g.index2Key(j));
                    List<Integer> accessible = g.getAccessible(j);
                    for (Integer integer : accessible) {
                        inDegreeArray[integer] -= 1;
                    }
                    break;
                }
            }
        }
        System.out.println(list);
        return null;
    }


}